package myjava.algorithm.leetcode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;
import java.util.Stack;

public class WordLadderII {
	int minValue = Integer.MAX_VALUE;
	HashMap<String,Integer> path = new HashMap<String,Integer>(); 
	
	public List<List<String>> findLadders(String start, String end, Set<String> dict) {
		
		List<List<String>> result = new ArrayList<List<String>>();
		
		ArrayList<String> list = new ArrayList<String>();
		
		bfs(start, end, dict);
		
		 dfs(end,start, dict, list, result);
    	
    	return result;
    }
	
	public void bfs(String start, String end, Set<String> dict) {
    	if (dict.size() == 0)  
            return;
    	
    	LinkedList<String> queue = new LinkedList<String>();
    	LinkedList<Integer> distant = new LinkedList<Integer>();
    	
    	queue.add(start);
    	distant.add(0);
    	path.put(start, 0);
    	
    	int min = 0;
    	
    	while(!queue.isEmpty())
    	{
    		String e = queue.pop();
    		int d = distant.pop();
    		
    		if(e.equals(end))
    			continue;
    		
    		for(int i= 0;i<e.length();i++)
    		{
    			char[] charArray = e.toCharArray();
    			
    			for(char a = 'a';a <= 'z';a++)
        		{
    				if(charArray[i]==a) {
                        continue;
                    }
    				
        			charArray[i]=a;
        			
        			String tempString = new String(charArray);
        			
        			if(dict.contains(tempString) || tempString.equals(end))
        			{
        				if(!path.containsKey(tempString))
        				{
	        				path.put(tempString, d+1);
	        				queue.add(tempString);
	        				distant.add(d + 1);
        				};
        			}
        			
        		}
    		}   		
    	}
    }
	
	public void dfs(String start, String end, Set<String> dict,ArrayList<String> list, List<List<String>> result) {
		if(start.equals(end)==true) {
            list.add(start);
            Collections.reverse(list);
            result.add(list);
            return;
        }
		
		if(!path.containsKey(start)) return;
		
		list.add(start);
		
		int nextDepth = (int)path.get(start) - 1;
		
		for(int i=0;i<start.length();i++) {
            char[] strCharArr = start.toCharArray();
            for(char ch='a';ch<='z';ch++) {
                if(strCharArr[i]==ch) {
                    continue;
                }
                strCharArr[i] = ch;
                String newWord = new String(strCharArr);

                if(path.get(newWord)!=null&&(path.get(newWord)==nextDepth)) {
                    ArrayList<String> newPathArray = new ArrayList<String>(list);
                    dfs(newWord,end,dict,newPathArray,result);
                }
            }
        }
    }
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Set<String> dict = new HashSet<String>();
		 dict.add("hot");
		 dict.add("dot");
		 dict.add("dog");
		 dict.add("lot");
		 //dict.add("lom");
		 //dict.add("lim");
		 //dict.add("lok");
		 dict.add("log");
		
		 
		/*dict.add("a");
		dict.add("b");
		dict.add("c");*/
		
		 WordLadderII w = new WordLadderII();
		 
		
		 System.out.println(w.findLadders("hit","cog",dict));
		 //System.out.println(w.findLadders("a","c",dict));
	}

}
